﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace CSharpAlgorithm.Base
{
    /// <summary>
    /// 세그먼트 트리
    /// RMQ를 O(log n)에 처리함
    /// </summary>
    class SegmentTree
    {
        private readonly int MAX_N = 1 << 17;
        private int n;
        private int[] dat;
        public SegmentTree(int _n)
        {
            dat = new int[2 * MAX_N - 1];
            n = 1;
            while (n < _n) n *= 2;
            for (int i = 0; i < 2 * n - 1; i++) 
            {
                dat[i] = Int32.MaxValue;
            }
        }
        public SegmentTree(int[] dat)
        {
            this.dat = dat;
            for (int i = 0; i < dat.Length; i++)
            {
                dat[i] = Int32.MaxValue;
            }
        }
        /// <summary>
        /// k번째 값을 a로 변경
        /// </summary>
        /// <param name="k"></param>
        /// <param name="a"></param>
        public void Update(int k, int a)
        {
            k += n - 1;
            dat[k] = a;
            while (k > 0)
            {
                k = (k - 1) / 2;
                dat[k] = Math.Min(dat[k * 2 + 1], dat[k * 2 + 2]);
            }
        }
        /// <summary>
        /// [a, b]의 최소값을 구함.
        /// </summary>
        public int Query(int a, int b)
        {
            return Query(a, b, 0, 0, n);
        }
        private int Query(int a, int b, int k, int l, int r)
        {
            if (r <= a || b <= l) return Int32.MaxValue;
            if (a <= l && r <= b) return dat[k];
            else
            {
                int vl = Query(a, b, k * 2 + 1, l, (l + r) / 2);
                int vr = Query(a, b, k * 2 + 2, (l + r) / 2, r);
                return Math.Min(vl, vr);
            }
        }
    }
}
